{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "# TESTING AND DEBUGGING\n",
    "\n",
    "<strong style=\"color:blue\">Testing</strong> is the process of running a program to try and ascertain whether or not  it <strong style=\"color:blue\">works as intended</strong>.\n",
    "\n",
    "<strong style=\"color:blue\">Debugging</strong> is the process of trying to <strong style=\"color:blue\">fix a program </strong>that you already know does not work as intended.\n",
    "\n",
    "Good programmers **design their programs** in ways that make them <strong style=\"color:blue\"><b style=\"color:red\">easy</b> to test and debug</strong>. \n",
    "\n",
    "The key to doing this is breaking the program up into <strong style=\"color:blue\">separate</strong> components </strong>that can be  <strong style=\"color:blue\">implemented </strong>，<strong style=\"color:blue\">tested </strong>，and <strong style=\"color:blue\">debugged</strong> **independently** of other components\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1 Testing\n",
    "\n",
    "The most important thing to say about testing is that its purpose is to  \n",
    " \n",
    " > **show that bugs `exist` , not to show that a program is bug-free**. \n",
    "\n",
    "Why is this so? Even the simplest of programs has **billions of possible inputs**. \n",
    "\n",
    "Consider, for example, a program that purports to meet the specification\n",
    "\n",
    "```python\n",
    "def is_smaller(x, y):\n",
    "   \"\"\"Assumes x and y are ints  \n",
    "     Returns True if x is less than y and False otherwise\"\"\"\n",
    "```\n",
    "Running it on **all** pairs of integers would be, to say the least, **tedious**. \n",
    "\n",
    "The best we can do is to run it on **pairs of integers** that have <strong style=\"color:blue\">a reasonable probability of producing the wrong answer</strong> if there is a bug in the program.\n",
    "\n",
    "### The Test Suite\n",
    "                                                                             The **key** to testing is <b style=\"color:blue\">finding</b> a collection of inputs, called  <b style=\"color:blue\">a test suite</b>, that has a high likelihood of <b style=\"color:blue\">revealing bugs, yet does not take too long to run</b>.\n",
    "\n",
    "### Constructing a test suite\n",
    "\n",
    "The key to doing this is **partitioning** the space of **all** possible inputs into <b style=\"color:blue\">subsets</b>t provide equivalent information about the correctness of the program, and then constructing **a test suite** that contains `at least one input from each partition`.\n",
    "\n",
    "### The example test suite\n",
    "\n",
    "Consider, for example, **is_smaller(x, y).** \n",
    "\n",
    "The set of possible inputs is all pairwise combinations of integers. \n",
    "\n",
    "One way to `partition this set` is into these **nine** subsets:\n",
    "\n",
    "* x positive, y positive (+，+） x < y\n",
    "* x positive, y positive (+，+） x > y\n",
    "* x negative, y negative (-，-） x < y\n",
    "* x negative, y negative (-，-） x > y\n",
    "* x positive, y negative (+，-）\n",
    "* x negative, y positive (-，+）\n",
    "* x = 0, y = 0\n",
    "* x = 0, y ≠ 0\n",
    "* x ≠ 0, y = 0\n",
    "\n",
    "If one tested the implementation on at least one value from each of these subsets, there would be reasonable probability (but no guarantee) of exposing a bug if one exists.\n",
    "\n",
    "**Heuristics**\n",
    "\n",
    "For most programs, `finding a good partitioning of the inputs` is far easier said than done. \n",
    "\n",
    "Typically, people rely on **heuristics** based on `exploring different paths` through some combination of the `code` and the `specifications` \n",
    "\n",
    "* **Black-Box**(黑箱）testing:  Heuristics based on `exploring paths` through the `specification`（基于软件功能描述设计测试路径的方法）\n",
    "\n",
    "* **Glass-Box**(白箱-White-Box）testing: Heuristics based on `exploring paths` through the `code`（基于代码分析设计测试路径的方法）\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1.1 Black-Box Testing\n",
    "\n",
    "In principle,black-box tests are constructed `without looking at the code` to be tested.\n",
    "\n",
    "Black-box testing allows **testers** and **implementers** to be drawn from `separate populations`.\n",
    "\n",
    ">  **testers** -- |separate| -- **implementers**\n",
    "\n",
    "**Positive feature of black-box**\n",
    "\n",
    "1. This independence **reduces** the likelihood of generating **test suites** that exhibit **mistakes** that are correlated with **`mistakes` in the code**. \n",
    "\n",
    "2. black-box testing is **robust** with respect to `implementation` **changes**.\n",
    "\n",
    "\n",
    "**The good ways to generate black-box test cases**\n",
    "\n",
    "* 1 `explore paths` through a  `specification`（基于软件功能描述设计测试数据)\n",
    "\n",
    "* 2 `Boundary conditions` should be tested.\n",
    "\n",
    "### 1  `explore paths` through a  `specification` \n",
    "\n",
    "Consider, the specification\n",
    "\n",
    "```python\n",
    "def sqrt(x, epsilon):\n",
    "    \"\"\"Assumes x, epsilon floats\n",
    "      x>= 0\n",
    "      epsilon > 0\n",
    "    Returns result such that\n",
    "       x-epsilon <= result*result <= x+epsilon\"\"\"   \n",
    "```\n",
    "There seem to be only `two distinct paths` through this specification: `x>= 0`\n",
    "\n",
    "* one corresponding to `x = 0` \n",
    "\n",
    "* one corresponding to `x > 0`. \n",
    "\n",
    "However, common sense tells us that while it is necessary to test these `two cases`, **it is hardly sufficient**\n",
    "\n",
    "### 2  Test Boundary conditions\n",
    "\n",
    "Boundary conditions should be tested\n",
    " \n",
    "#### 2.1 Boundary conditions of `lists`\n",
    "\n",
    " Looking at an argument of type list often means looking at the \n",
    " \n",
    "* `empty` list,\n",
    "\n",
    "* a list with exactly `one element`\n",
    "\n",
    "* a list `containing lists.`\n",
    "\n",
    "#### 2.2  Boundary conditions of  `numbers`\n",
    "\n",
    "It typically means looking at \n",
    "\n",
    "* `very small` values\n",
    "\n",
    "* `very large` values\n",
    "\n",
    "* `typical` values. \n",
    "\n",
    "For <b style=\"color:blue\">sqrt</b>, for example, it might make sense to try values of `x` and `epsilon` similar to those in the figure\n",
    "\n",
    "![figure61](./img/ee/fig61.jpg)\n",
    "\n",
    "**The `first four rows`** are intended to represent `typical` cases. \n",
    "\n",
    "* the values for x include a perfect square,) $0*0=0$,$5*5=25$\n",
    "\n",
    "* a number less than one, $0.5$\n",
    "\n",
    "* a number with an irrational square root.values $0.5$,$2.0$\n",
    "\n",
    "If any of these tests fail, there is a bug in the program that needs to be fixed.\n",
    "\n",
    "\n",
    "**The remaining rows** test\n",
    "\n",
    "* `extremely large and small values` of **x and epsilon**. \n",
    "\n",
    "If any of these tests **fail**, something needs to be fixed.**Perhaps**\n",
    "\n",
    "* **1** `a bug in the code` needs to be fixed\n",
    "\n",
    "* **2** the `specification` needs to be changed so that it is easier to meet. \n",
    "\n",
    "  * It might, for example, be unreasonable to expect to find an approximation of a square root when `epsilon` is **ridiculously small**.\n",
    "\n",
    "#### 2.3 Boundary condition of  `aliasing`. \n",
    "  \n",
    "Consider, for example, the code"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def copy(L1, L2):\n",
    "    \"\"\"Assumes L1, L2 are lists\n",
    "       Mutates L2 to be a copy of L1\"\"\"\n",
    "    \n",
    "    while len(L2) > 0: # remove all elements from L2\n",
    "        L2.pop()       # remove last element of L2\n",
    "    \n",
    "    for e in L1:       # append L1's elements to initially empty L2\n",
    "        L2.append(e)        "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It will **work** most of the time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "L1 [1, 2, 3, 4]\n",
      "L2 [1, 2, 3, 4]\n"
     ]
    }
   ],
   "source": [
    "L1=[1,2,3,4]\n",
    "L2=[2,3,4,5]\n",
    "copy(L1, L2)\n",
    "print(\"L1\",L1)\n",
    "print(\"L2\",L2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "L1 [1, 2, 3, 4]\n",
      "L2 [1, 2, 3, 4]\n"
     ]
    }
   ],
   "source": [
    "L1=[1,2,3,4]\n",
    "L2=[1,2,3,4]\n",
    "copy(L1, L2)\n",
    "print(\"L1\",L1)\n",
    "print(\"L2\",L2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**BUT** when L1 and L2 refer to **the same list**(the same object)  **？** \n",
    "\n",
    "Any test suite that did not include a call of the form \n",
    "```python\n",
    "copy(L, L)\n",
    "```\n",
    "would not reveal the bug"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "L1 []\n",
      "L2 []\n",
      "1949290413120\n",
      "1949290413120\n"
     ]
    }
   ],
   "source": [
    "L1=[1,2,3,4]\n",
    "L2=L1    #  L1 and L2 refer to the same list. aliasing: 别名混叠\n",
    "copy(L1, L2)\n",
    "print(\"L1\",L1)\n",
    "print(\"L2\",L2)\n",
    "# refer to the same list. aliasing\n",
    "print(id(L1))\n",
    "print(id(L2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## 1.2  Glass-Box Testing\n",
    "\n",
    "**`Black-box` testing should never be skipped, but it is `rarely` sufficient**. \n",
    "\n",
    "Without looking at the internal structure of the code,\n",
    "\n",
    "* it is **impossible** to know `which test cases` are likely to `provide new information`. \n",
    "\n",
    "**The Glass-Box method to constructing the test cases from the program `logic or the code` written**\n",
    "\n",
    "\n",
    "Consider the trivial example:\n",
    "\n",
    "* A **prime** number(质数) is a natural number greater than 1 that has no positive divisors other than 1 and itself"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "def isPrime(x):\n",
    "    \"\"\"Assumes x is a non-negative int\n",
    "       Returns True if x is prime; False otherwise\"\"\"\n",
    "    if x <= 2:  # bug\n",
    "        return False\n",
    "    \n",
    "    for i in range(2, x):\n",
    "        if x%i == 0:\n",
    "           return False\n",
    "    \n",
    "    return True"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Looking at the code**,\n",
    "\n",
    "we can see that \n",
    "\n",
    "* because of the test <b style=\"color:blue\">if x <= 2 </b>, the values `0, 1, and 2` are treated as `special cases`, and therefore need to be tested. \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "isPrime(2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Without looking at the code**, \n",
    "\n",
    "one might `not test` **isPrime(2)**, and would therefore not discover that the function call **isPrime(2)** returns `False`, erroneously indicating that 2 is not a prime"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<b>Glass-box test suites</b> are usually much <b>easier to construct</b> than black-box test suites.\n",
    "\n",
    "A glass-box test suite is <b>path-complete</b> \n",
    "\n",
    "* if it exercises **every potential path** through the program. \n",
    "\n",
    "But, \n",
    "\n",
    "**1** this is typically `impossible` to achieve.\n",
    "\n",
    "because it depends upon `the number of times each loop` is executed and `the depth of each recursion`.\n",
    "\n",
    "For example, a recursive implementation of **factorial** follows a different path for each possible input(because the number of levels of recursion will differ).\n",
    "\n",
    "**2** even a `path-complete` test suite does `not guarantee` that `all` bugs will be exposed.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "def iabs(x):\n",
    "    \"\"\"Assumes x is an int\n",
    "       Returns x if x>=0 and –x otherwise\"\"\"\n",
    "    if x < -1:     # bug: iabs(-1) will return -1.\n",
    "        return -x\n",
    "    else:\n",
    "        return x"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The **specification**  <b style=\"color:blue\"> if x>=0</b> suggests that there are two possible cases: \n",
    "\n",
    "* `x` is <b style=\"color:blue\">negative</b> \n",
    "\n",
    "* `x` <b style=\"color:blue\">isn’t negative.</b>\n",
    "\n",
    "This suggests that the set of inputs {2, -2} is sufficient to explore  <b>all paths(a path-complete test suite)</b> in the specification.\n",
    "```python\n",
    " 2     isn’t negative\n",
    "\n",
    "-2     negative\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "iabs(2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "iabs(-2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**BUT**: The only problem is that this <b>path-complete</b> test suite  will not expose the fact that\n",
    "\n",
    "* ```iabs(-1)``` will return ```-1```."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "-1"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "iabs(-1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "#### 2 A few rules of thumb of  the glass-box testing\n",
    "\n",
    "Despite the limitations of **glass-box** testing, There are **a few rules of thumb** that are usually worth following:\n",
    "    \n",
    "**if** statements: \n",
    "\n",
    "* Exercise **both** branches of all `if` statements\n",
    "\n",
    "\n",
    "**except** clause: \n",
    "\n",
    "*  Make sure that each `except` clause (see Chapter 7) is executed\n",
    "\n",
    "\n",
    "**for** loop:\n",
    "\n",
    "For each `for` loop, have **test cases** in which\n",
    "  \n",
    "  * The loop is `not entered` (e.g.,if the loop is iterating over the elements of a list, make sure that it is tested on the `empty` list),\n",
    " \n",
    "  * The body of the loop is executed `exactly once`\n",
    "\n",
    "  * The body of the loop is executed `more than once`\n",
    "\n",
    "\n",
    "**while** loop: \n",
    "\n",
    "For each `while` loop,\n",
    "\n",
    "* Look at the `same` kinds of cases as when dealing with `for` loops.\n",
    "   \n",
    "* Include test cases corresponding to `all possible ways` of **exiting** the loop.\n",
    "\n",
    "For example, for a loop starting with\n",
    "\n",
    "```python\n",
    "     while len(L) > 0 and not L[i] == e\n",
    "```\n",
    "find cases where the loop exits because `len(L) is greater than zero` and cases where it exits because `L[i] == e`.\n",
    "\n",
    "**recursive functions**: \n",
    "\n",
    "For `recursive functions`, include test cases that cause the function to return \n",
    "\n",
    "* with `no recursive` calls, \n",
    "\n",
    "* exactly `one recursive` call, \n",
    "\n",
    "* `more than one` recursive call."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## 1.3 Conducting Tests\n",
    "\n",
    "**Testing** is often thought of as occurring in **these phases**: \n",
    "\n",
    "\n",
    "### Unit testing\n",
    "\n",
    "During this phase testers construct and run tests designed to ascertain whether **individual units** of code (e.g., functions) work properly.\n",
    "\n",
    "One should always **start** with **unit testing**.\n",
    "\n",
    "### Integration testing\n",
    "\n",
    "This is followed by  <b>integration testing</b>,which is designed to ascertain whetherthe program as **a whole** behaves as intended.\n",
    "\n",
    "### functional testing\n",
    "\n",
    "Finally, functional testing is used to check if the program as a whole behaves as intended\n",
    "\n",
    "In practice, testers **cycle** through these phases, since failures during integration or functional testing lead to making changes to individual units\n",
    "\n",
    "Functional testing is almost always the most challenging phase. The intended behavior of an entire program is considerably harder to characterize than the in-tended behavior of each of its parts.\n",
    "\n",
    "For example, characterizing the intended be-havior of a word processor is considerably more challenging than characterizing the behavior of the subsystem that counts the number of characters in a docu-ment. Problems of scale can also make functional testing difficult. It is not unusual for functional tests to take hours or even days to run.\n",
    "\n",
    "### test drivers(测试驱动程序)\n",
    "\n",
    "In industry, the testing process is often highly **automated**. Testers do not sit at terminals typing inputs and checking outputs. Instead, they use **test drivers** that autonomously \n",
    "\n",
    "* Set up the `environment` needed to invoke the program (or unit) to be tested,\n",
    "\n",
    "* `Invoke the program` (or unit) to be tested with a predefined or automatically generated sequence of inputs,\n",
    "\n",
    "* `Save the results` of these invocations,\n",
    "\n",
    "* Check the `acceptability of the result`s of the tests, and\n",
    "\n",
    "* Prepare an appropriate `report`.\n",
    "\n",
    "**Python Testing Frameworks**\n",
    "\n",
    "* [Unittest：automated unit test framework](./Unittest_Python.ipynbtest_Python.ipynb)\n",
    "\n",
    "* [Robot Framework](https://robotframework.org/) \n",
    "\n",
    "* [Selenium automates browsers](https://www.selenium.dev/)\n",
    "\n",
    "#### stubs(存根/桩单元)\n",
    "\n",
    "During <b style=\"color:blue\">unit testing</b>, we often need to build <b style=\"color:blue\">stubs(存根/桩单元)</b> as well as <b style=\"color:blue\"> drivers</b>. <b style=\"color:blue\">Drivers</b> simulate parts of the program that `use the unit` being tested, whereas <b style=\"color:blue\">stubs</b> simulate parts of the program used by the unit `being tested`. **Stubs** are useful because they allow people to test units that depend upon software or sometimes even hardware that **does not yet exist**. This allows teams of programmers to `simultaneously` develop and test multiple parts of a system.\n",
    "\n",
    "Ideally, a stub should\n",
    "\n",
    "* Check the reasonableness of the environment and arguments supplied by the caller (calling a function with inappropriate arguments is a common error). \n",
    "\n",
    "* Modify arguments and global variables in a manner consistent with the specification.\n",
    "\n",
    "* Return values consistent with the specification\n",
    "\n",
    "### Regression testing\n",
    "\n",
    "One attraction of automating the testing process is that it facilitates `regression testing`.\n",
    "\n",
    "As programmers attempt to debug a program, it is all too common to install a “fix” that `breaks something that used to work`. \n",
    "\n",
    "Whenever `any change` is made, no matter how small, you should check that the program `still passes all of the tests` that it used to pass."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2 Debugging\n",
    "\n",
    "There is a charming urban legend about how the process of fixing flaws in software came to be known as debugging.\n",
    "\n",
    "`Runtime bugs` can be categorized along two dimensions:\n",
    "\n",
    "**(1)Overt → covert:**\n",
    "\n",
    "* An **overt** bug has an **obvious** manifestation\n",
    "   \n",
    "* A **covert** bug has **no obvious** manifestation.\n",
    "   \n",
    "Many bugs fall between the two extremes\n",
    "   \n",
    "   \n",
    "**(2) Persistent → intermittent:**\n",
    "\n",
    "* A **persistent** bug occurs **every time** the  program is run with the same inputs.\n",
    "   \n",
    "* An **intermittent** bug occurs only **some of the time**, even when the program is run on the same inputs and seemingly under the same conditions.\n",
    "\n",
    "**A)** The **best kinds of bugs** to have are **overt and persistent**.\n",
    " \n",
    ">Good programmers try to write their programs in such a way that programming  mistakes lead to bugs that are both **overt and persistent**. \n",
    "\n",
    ">This is often called **defensive programming** : the practice of writing programs that check their own operation to catch errors **as early as possible**\n",
    "\n",
    "\n",
    "**B)** The next step into the pit of undesirability is bugs that are <b>overt but intermittent</b>.\n",
    "   \n",
    "**C)** Programs that fail in <b>covert</b> ways are often <b>highly dangerous</b>.\n",
    "\n",
    "Bugs that are both <b>covert and intermittent</b> are almost always the <b>hardest</b> to find and fix."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.1 Learning to Debug\n",
    "\n",
    "#### Debugging is a learned skill.\n",
    "\n",
    "The good news is  that it’s not hard to learn, and it is a transferable skill.\n",
    "\n",
    "Most programmers say that \n",
    "\n",
    ">the most important debugging tool is the **print** statement.\n",
    "\n",
    "**Debugging** is the process of **searching** for an explanation of that behavior. \n",
    "\n",
    "The key to being consistently **good at debugging** is being **systematic** in conducting that **search**.\n",
    "\n",
    "* 1 Start by **studying the available data**: the test results and the program text\n",
    "\n",
    "\n",
    "* 2 form a **hypothesis** that you believe to be consistent with all the data\n",
    "\n",
    "\n",
    "* 3 design and run **a repeatable experiment** with the potential to **refute** the hypothesis\n",
    "\n",
    "\n",
    "* 4 Finally, it’s important to keep **a record of what experiments**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "### 2.2 Designing the Experiment\n",
    "\n",
    "Think of **debugging** as **a search process**, and \n",
    "\n",
    "> each **experiment** as an attempt to **reduce the size of the search space****. \n",
    "\n",
    "**1 One way** to reduce the size of the search space is to design an experiment \n",
    "\n",
    "    that can be used to decide whether **a specific region of code** is responsible for a problem uncovered during integration testing.\n",
    "\n",
    "**2 Another way** to reduce the search space is to\n",
    "\n",
    "**reduce the amount of test data** needed to provoke a manifestation of a bug.\n",
    "\n",
    "#### Let’s look at a contrived example to see how one\n",
    "\n",
    "A **palindrome** is a word, phrase, number, or other sequence of characters which reads the same backward or forward\n",
    "\n",
    "```\n",
    "\"race car\"\n",
    "\"rac ecar\"\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "def is_pal(x):\n",
    "    \"\"\"Assumes x is a list\n",
    "       Returns True if the list is a palindrome; False otherwise\"\"\"\n",
    "    temp = x\n",
    "    temp.reverse\n",
    "    return temp == x\n",
    "\n",
    "def silly(n):\n",
    "    \"\"\"Assumes n is an int > 0\n",
    "       Gets n inputs from user\n",
    "       Prints 'Yes' if the sequence of inputs forms a palindrome;\n",
    "           'No' otherwise\"\"\"\n",
    "    for i in range(n):\n",
    "        result = []\n",
    "        elem = input('Enter element: ')\n",
    "        result.append(elem)\n",
    "    if is_pal(result):\n",
    "        print('Yes')\n",
    "    else:\n",
    "        print('No')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You could try and test it on the supplied 1000 -string input. But it might be more\n",
    "sensible to begin by trying it on something smaller. In fact, it would make sense\n",
    "to test it on a minimal non-palindrome, e.g.,\n",
    "```\n",
    "ab\n",
    "\n",
    "ba\n",
    "```\n",
    "palindrome> -> No"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Enter element: a\n",
      "Enter element: b\n",
      "Yes\n"
     ]
    }
   ],
   "source": [
    "silly(2)  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The **good** news is that it **fails** even this **simple** test, so you don’t have to type in a thousand strings - **small test data** \n",
    "\n",
    "The **bad** news is that you have no idea why it failed.\n",
    "\n",
    "In this case, the **code** is **small** enough that you can probably **stare** at it and find the bug (or bugs). \n",
    "\n",
    "However, let’s pretend that it is **too large** to do this, and start to systematically reduce the search space - **code**\n",
    "\n",
    "#### Looking at `silly`\n",
    "\n",
    "**1** The first thing to `check` is whether `result` has the expected value, ```['a', 'b']```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1.  We check this by inserting the statement \n",
    "```python\n",
    "print(result)\n",
    "```\n",
    "before \n",
    "```python\n",
    " if isPal(result):\n",
    "``` "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "      \n",
    "def silly(n):\n",
    "    \"\"\"Assumes n is an int > 0\n",
    "    Gets n inputs from user\n",
    "    Prints 'Yes' if the sequence of inputs forms a palindrome;\n",
    "    'No' otherwise\"\"\"\n",
    "    result = []\n",
    "    for i in range(n):\n",
    "        elem = input('Enter element: ')\n",
    "        result.append(elem)\n",
    "     # 1. inserting the statement print result \n",
    "    print(result)\n",
    "    if is_pal(result):\n",
    "        print('Yes')\n",
    "    else:\n",
    "        print('No')        "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "When the experiment is run"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Enter element: a\n",
      "Enter element: b\n",
      "['a', 'b']\n",
      "Yes\n"
     ]
    }
   ],
   "source": [
    "silly(2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The program \n",
    "```\n",
    "prints(result)  -> ['b'] not ['a','b']\n",
    "```\n",
    "suggest  that something has already gone wrong. \n",
    "\n",
    "**2 The next step is to** \n",
    "\n",
    "check the input loop, <b style=\"color:blue\"> print `result` through the `loop`.</b>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "def silly(n):\n",
    "    \"\"\"Assumes n is an int > 0\n",
    "       Gets n inputs from user\n",
    "       Prints 'Yes' if the sequence of inputs forms a palindrome;\n",
    "       'No' otherwise\"\"\"\n",
    "    for i in range(n):\n",
    "       \n",
    "        result = [] \n",
    "      \n",
    "        elem = input('Enter element: ')\n",
    "        result.append(elem)\n",
    "        \n",
    "        # 2 print result roughly halfway through the loop.\n",
    "        print('loop region: ',result) #  print result roughly halfway through the loop.\n",
    "    \n",
    "    \n",
    "    # 1 inserting the statement print result \n",
    "    print(result) \n",
    "    \n",
    "    if isPal(result):\n",
    "        print('Yes')\n",
    "    else:\n",
    "        print('No')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Enter element: a\n",
      "loop region:  ['a']\n",
      "Enter element: b\n",
      "loop region:  ['b']\n",
      "['b']\n",
      "Yes\n"
     ]
    }
   ],
   "source": [
    "silly(2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "    print('loop region: ',result)\n",
    "\n",
    "    loop region:  ['a']\n",
    "    loop region:  ['b']\n",
    "\n",
    "This quickly **reveals** that \n",
    "\n",
    "```python\n",
    "for i in range(n):\n",
    "```\n",
    "result is <b style=\"color:blue\">never more than `one element` long</b>, \n",
    "\n",
    "suggesting that the <b style=\"color:blue\">initialization of result \n",
    "```python\n",
    "for i in range(n):\n",
    "  result = [] \n",
    "```\n",
    "needs to be moved **outside** the for loop</b>. \n",
    "```python\n",
    "result = [] \n",
    "for i in range(n)\n",
    "```    \n",
    "The corrected code for `silly` is"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "def silly(n):\n",
    "    \"\"\"Assumes n is an int > 0\n",
    "       Gets n inputs from user\n",
    "       Prints 'Yes' if the sequence of inputs forms a palindrome;\n",
    "       'No' otherwise\"\"\"\n",
    "   \n",
    "    # remove Bug 1 \n",
    "    result = [] # initialization of result needs to be moved outside the for loop\n",
    "    \n",
    "    for i in range(n):\n",
    "        elem = input('Enter element: ')\n",
    "        result.append(elem)\n",
    "       \n",
    "        # 2 print result roughly halfway through the loop\n",
    "        print('loop region: ',result) \n",
    "    \n",
    "    # 1 inserting the statement print result\n",
    "    print(result) \n",
    "    \n",
    "    if is_pal(result):\n",
    "        print('Yes')\n",
    "    else:\n",
    "        print('No')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Enter element: a\n",
      "loop region:  ['a']\n",
      "Enter element: b\n",
      "loop region:  ['a', 'b']\n",
      "['a', 'b']\n",
      "Yes\n"
     ]
    }
   ],
   "source": [
    "silly(2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let’s try that, and see if `result` has the `correct` value after the for loop.\n",
    "\n",
    "It does\n",
    "```\n",
    "Enter element: a\n",
    "loop region:  ['a']\n",
    "Enter element: b\n",
    "loop region:  ['a', 'b']\n",
    "```\n",
    "but `unfortunately` the program still printsL: **Yes**.\n",
    "\n",
    "We have reason to believe that **a second bug** lies **below the print statement**.\n",
    "\n",
    "```python\n",
    "if isPal(result):\n",
    "```\n",
    "\n",
    "lets look <b>isPal</b>\n",
    "\n",
    "we `insert` the line \n",
    "```python\n",
    "print('\\n temp,x',temp,x)\n",
    "```\n",
    "before that line:\n",
    "```python\n",
    "if temp == x:\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "def is_pal(x):\n",
    "    \"\"\"Assumes x is a list\n",
    "       Returns True if the list is a palindrome; False otherwise\"\"\"\n",
    "    temp = x\n",
    "    \n",
    "    temp.reverse \n",
    "    \n",
    "    # 3 insert the line print temp, x before that line: if temp == x:\n",
    "    print('\\n temp,x',temp,x)\n",
    "    \n",
    "    if temp == x:\n",
    "        return True\n",
    "    else:\n",
    "        return False\n",
    "    \n",
    "def silly(n):\n",
    "    \"\"\"Assumes n is an int > 0\n",
    "       Gets n inputs from user\n",
    "       Prints 'Yes' if the sequence of inputs forms a palindrome;\n",
    "       'No' otherwise\"\"\"\n",
    "     \n",
    "    result = [] # initialization of result needs to be moved outside the for loop\n",
    "    \n",
    "    for i in range(n):\n",
    "        elem = input('Enter element: ')\n",
    "        result.append(elem)\n",
    "    \n",
    "        print('loop region: ',result) # 2 print result roughly halfway through the loop\n",
    "    \n",
    "    print(result) # 1 inserting the statement print result\n",
    "    \n",
    "    if is_pal(result):\n",
    "        print('Yes')\n",
    "    else:\n",
    "        print('No')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Enter element: a\n",
      "loop region:  ['a']\n",
      "Enter element: v\n",
      "loop region:  ['a', 'v']\n",
      "['a', 'v']\n",
      "\n",
      " temp,x ['a', 'v'] ['a', 'v']\n",
      "Yes\n"
     ]
    }
   ],
   "source": [
    "silly(2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "discover that both `temp` and `x` have the <b>non-reverse</b> value\n",
    "\n",
    "```\n",
    "['a', 'b'].\n",
    "```\n",
    "\n",
    "A quick inspection of the code reveals that in `isPal` \n",
    "\n",
    "we wrote\n",
    "```python\n",
    "temp.reverse\n",
    "```\n",
    "rather than\n",
    "```python\n",
    "temp.reverse()\n",
    "```\n",
    "\n",
    "the evaluation of `temp.reverse` returns the built-in `reverse method object` for lists, but does not `invoke` it."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**returns the built-in the method object**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "<built-in method reverse of list object at 0x7f8ab1785048>\n"
     ]
    }
   ],
   "source": [
    "r=['a','b']\n",
    "r=r.reverse\n",
    "print(r)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`invoke` the method: `method()`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "['b', 'a']\n"
     ]
    }
   ],
   "source": [
    "r=['a','b']\n",
    "r.reverse() ## method()\n",
    "print(r)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "def is_pal(x):\n",
    "    \"\"\"Assumes x is a list\n",
    "       Returns True if the list is a palindrome; False otherwise\"\"\"\n",
    "    temp = x  \n",
    "    \n",
    "    # remove Bug2:  \n",
    "    temp.reverse() # temp.reverse -> temp.reverse()\n",
    "    \n",
    "    print('\\n temp,x',temp,x)\n",
    "    \n",
    "    if temp == x:\n",
    "        return True\n",
    "    else:\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Enter element: a\n",
      "loop region:  ['a']\n",
      "Enter element: b\n",
      "loop region:  ['a', 'b']\n",
      "['a', 'b']\n",
      "\n",
      " temp,x ['b', 'a'] ['b', 'a']\n",
      "Yes\n"
     ]
    }
   ],
   "source": [
    "silly(2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We run the test again, and now it seems that **both** `temp and x` have the <b>reverse</b> value \n",
    "\n",
    "['b', 'a']. \n",
    "\n",
    "We have now **narrowed** the bug to **one line**.\n",
    "\n",
    "It seems that **temp.reverse()** `unexpectedly` changed the value of **x**\n",
    "\n",
    "<b style=\"color:blue\">An `aliasing` bug has bittenus</b>: \n",
    "\n",
    ">`temp` and `x` are names for the same list, \n",
    "\n",
    "both before and after the list gets reversed. \n",
    "\n",
    "One way to fix it is to replace the first assignment statement in `isPal` by \n",
    "```python\n",
    "temp = x[:]\n",
    "```\n",
    "which causes a **copy** of x to be made. (Ref **P63 5.2.1 Cloning**)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "def is_pal(x):\n",
    "    \"\"\"Assumes x is a list\n",
    "       Returns True if the list is a palindrome; False otherwise\"\"\"\n",
    "   \n",
    "    # remove Bug 3 An aliasing bug\n",
    "    temp = x[:] #   a copy of x : temp = x ->temp = x[:]\n",
    "    \n",
    "    # remove Bug 2\n",
    "    temp.reverse()  # temp.reverse -> temp.reverse()\n",
    "    print('\\n temp,x',temp,x)\n",
    "    if temp == x:\n",
    "        return True\n",
    "    else:\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Enter element: a\n",
      "loop region:  ['a']\n",
      "Enter element: b\n",
      "loop region:  ['a', 'b']\n",
      "['a', 'b']\n",
      "\n",
      " temp,x ['b', 'a'] ['a', 'b']\n",
      "No\n"
     ]
    }
   ],
   "source": [
    "silly(2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### THREE BUGS :\n",
    "\n",
    "**BUG 1**: `never more than one` element long: ['b'] \n",
    "\n",
    "Failed to `reinitialize` a variable\n",
    "\n",
    "```python\n",
    "      for i in range(n):\n",
    "        result = []\n",
    "```\n",
    "\n",
    "`initialization` of result needs to be moved `outside the for loop`\n",
    "\n",
    "```python   \n",
    "    result = [] \n",
    "    for i in range(n):\n",
    "```   \n",
    "\n",
    "**BUG 2**  both `temp` and `x` have the `non-reverse` value ['a', 'b']: \n",
    "\n",
    "Forgotten the `()` that turns `a reference to an object` of type function into a function `invocation`\n",
    "\n",
    "```python\n",
    "temp.reverse \n",
    "```   \n",
    "add `()`\n",
    "\n",
    "```python    \n",
    "temp.reverse()\n",
    "```  \n",
    "\n",
    "**BUG 3** both `temp` and `x` have the `reverse` value [ 'b','a']: \n",
    "\n",
    "An `aliasing` bug: Created an unintentional alias\n",
    "\n",
    "```python    \n",
    "temp = x\n",
    "```\n",
    "cloning\n",
    "\n",
    "```python\n",
    "temp = x[:]\n",
    "```\n",
    "#### Print Location: before and after:  the key locations\n",
    "\n",
    "* **block**\n",
    "\n",
    "\n",
    "* **logic**\n",
    "\n",
    "\n",
    "* **operation**\n",
    "\n",
    "\n",
    "Step by Step to **reduce** the size of search space "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.3 When the Going Gets Tough\n",
    "\n",
    "Joseph P. Kennedy, father of U.S. President John F. Kennedy, reputedly instructed his  children,\n",
    "\n",
    "\n",
    "* <b style=\"color:blue;font-size:200%\">When the going gets tough,the tough get going</b>\n",
    "\n",
    "---\n",
    "This subsection contains a few pragmatic hints about what do when the debugging gets tough.\n",
    "* <b style=\"color:blue\">Look for the usual suspects</b>\n",
    "    * Passed arguments to a function in the **wrong order**\n",
    "\n",
    "    * **Misspelled** a name, e.g., typed a lowercase letter when you should have typed an uppercase one\n",
    "   \n",
    "    * **Failed to reinitialize** a variable\n",
    "   \n",
    "    * Tested that two floating point values are **equal (==)** instead of **nearly** equal (remember that floating point arithmetic is not the same as the arithmetic you learned in school)\n",
    "   \n",
    "    * Tested for `value equality` (e.g., compared two lists by writing the expression L1 == L2) when you meant **object equality** (e.g.id(L1) == id(L2))\n",
    "  \n",
    "    * Forgotten that some built-in function has a **side** effect\n",
    "  \n",
    "    * **Forgotten the ()** that turns a reference to an object of type function into a function **invocation**\n",
    "  \n",
    "    *  Created an `unintentional alias` \n",
    "  \n",
    "    *  Made any other mistake that is **typical for you**\n",
    "---  \n",
    "* <span style=\"color:blue\">Stop asking yourself why the program isn’t doing what you want it to.Instead, ask yourself why it is doing what it is.</span>. That should be an easier question to answer, and will probably be a good first step in figuring out how to fix the program.\n",
    "\n",
    "\n",
    "* <span style=\"color:blue\">Keep in mind that the bug is probably not where you think it is</span>.If it were, you would probably have found it long ago. One practical way to go about deciding where to look is asking where the bug cannot be. As Sherlock Holmes said,“Eliminate all other factors, and the one which remains must be the truth.”\n",
    "\n",
    "\n",
    "* <span style=\"color:blue\">Try to explain the problem to somebody else</span> We all develop blind spots. It is often the case that merely attempting to explain the problem to someone will lead you to see things you have missed. A good thing to try to explain is why the bug\n",
    "cannot be in certain places.\n",
    "\n",
    "\n",
    "* <span style=\"color:blue\">Don’t believe everything you read</span>. In particular, don’t believe the documentation. The code may not be doing what the comments suggest.\n",
    "\n",
    "\n",
    "* <span style=\"color:blue\">Stop debugging and start writing documentation</span> This will help you approach the\n",
    "problem from a different perspective.\n",
    "\n",
    "\n",
    "* <span style=\"color:blue\">Walk away, and try again tomorrow</span> This may mean that bug is fixed later in time than if you had stuck with it, but you will probably spend a lot less of your time looking for it. That is, it is possible to trade latency for efficiency. \n",
    "\n",
    "\n",
    "**Students, this is an excellent reason to start work on programming problem sets earlier rather than later!**\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "### 2.4 And When You Have Found “The” Bug\n",
    "\n",
    "When you think you have found a bug in your code, the temptation to start coding and testing a fix is almost irresistible. \n",
    "\n",
    "<b style=\"color:blue\">It is often better, however, to slow down a little.</b>\n",
    "\n",
    "Remember that the goal is not to fix one bug, but to move rapidly and efficiently towards a bug-free program.\n",
    "\n",
    "<span style=\"color:blue\"> Ask yourself if this bug explains all the observed symptoms, or whether it is just the tip of the iceberg</span>. \n",
    "\n",
    "If the latter, it may be better to think about taking care of this bug in concert with other changes. \n",
    "\n",
    "Suppose, for example, that you have discovered that the bug is the result of having accidentally `mutated a list`. You could circumvent the problem locally, perhaps by making a copy of the list. Alternatively, you could consider `using a tuple instead of a list` (since tuples are immutable), perhaps eliminating imilar bugs elsewhere in the code.\n",
    "\n",
    "<span style=\"color:blue\">Before making any change, try and `understand the ramification` of the proposed “fix.”</span>.\n",
    "\n",
    "Will it break something else? Does it introduce excessive complexity? Does it offer the opportunity to tidy up other parts of the code?\n",
    "\n",
    "\n",
    "<span style=\"color:blue\">Always make sure that you can `get back` to where you are </span>.\n",
    "\n",
    "There is nothing more frustrating than realizing that a long series of changes have left you farther from the goal than when you started, and having no way to get back to where you started. Disk space is usually plentiful. Use it to store old versions of your program:\n",
    "   \n",
    "* **Using Verison Control for your projects**: git and github\n",
    "\n",
    "<span style=\"color:blue\">Finally, if there are many `unexplained` errors</span>,\n",
    "\n",
    "you might consider whether finding and fixing bugs one at a time is even the right approach.\n",
    "\n",
    "Maybe you would be better off thinking about whether there is some better way to **organize your program or some simpler algorithm** that will be **easier** to implement correctly.\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3.8.7 64-bit",
   "name": "python387jvsc74a57bd02db524e06e9f5f4ffedc911c917cb75e12dbc923643829bf417064a77eb14d37"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.7"
  },
  "latex_envs": {
   "LaTeX_envs_menu_present": true,
   "autoclose": false,
   "autocomplete": true,
   "bibliofile": "biblio.bib",
   "cite_by": "apalike",
   "current_citInitial": 1,
   "eqLabelWithNumbers": true,
   "eqNumInitial": 1,
   "hotkeys": {
    "equation": "Ctrl-E",
    "itemize": "Ctrl-I"
   },
   "labels_anchors": false,
   "latex_user_defs": false,
   "report_style_numbering": false,
   "user_envs_cfg": false
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": false,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {
    "height": "calc(100% - 180px)",
    "left": "10px",
    "top": "150px",
    "width": "307.2px"
   },
   "toc_section_display": true,
   "toc_window_display": true
  },
  "widgets": {
   "state": {},
   "version": "1.1.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
